package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

/**
 * 排序链表
 * 2025-02-26 16:57:38
 * 时间复杂度：O(n log n)
 * 空间复杂度：O(log n)
 */
class SortList {

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 递归终止条件：链表为空或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        // 找到链表的中点
        ListNode mid = findMiddle(head);
        ListNode rightHead = mid.next; // 右半部分的头节点
        mid.next = null; // 断开链表

        // 递归排序左半部分和右半部分
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 合并两个有序链表
        return mergeTwoLists(left, right);
    }
    // 找到链表的中点（快慢指针法）
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next; // fast 从 head.next 开始，确保 slow 指向中点或左中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode();
        ListNode pre = dummy;
        while (l1!=null&&l2!=null){
            if(l1.val<l2.val){
                pre.next = l1;
                l1=l1.next;
            }else{
                pre.next = l2;
                l2=l2.next;
            }
            pre=pre.next;
        }
        pre.next = l1==null?l2:l1;
        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new SortList().new Solution();
        ListNode listNode = new ListNode(4);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(1);
        listNode.next.next.next = new ListNode(3);
        ListNode listNode1 = solution.sortList(listNode);
        while (listNode1!=null){
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }
    }
}